#!/usr/bin/env python
#coding=utf-8
#author=xiaomayi0323
#date=2009/04/09
#filename=5-15

#!/usr/bin/env python

#欧几里德算法
def gcd1(x, y):
    if y == 0:
        return x
    else:
        return gcd1(y, x%y)

def gcd2(x, y):
    if x%y == 0:
        return x
    else:
        return gcd2(y, x%y)

# Stein算法
def gcd3(x, y):
    if x < y:
       x, y = y, x
    if y == 0:
        return x
    if x&1 == 0 and y&1 == 0:                           # x%2 == 0
        return 2*gcd3(x>>1, y>>1)                  # x/2
    if x&1 == 0:
        return gcd3(x>>1, y)
    if y&1 == 0:
        return gcd3(x, y>>1)

    return gcd3((x+y)>>1, (x-y)>>1)

def lcm(x, y):
    return x*y/gcd3(x, y)

if __name__ == '__main__':
    x = 12
    y = 16
    assert x != 0 and y != 0
    print gcd1(x, y)
    print gcd2(x, y)
